import java.util.Stack;

/**
 * 1123. 最深叶节点的最近公共祖先
 */
public class No1123 {
    int dep = -1;
    Stack<TreeNode> stack = new Stack<>();

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        return dfs(root, -1);
    }

    /**
     * 计算深度最大值
     */
    public TreeNode dfs(TreeNode node, int cur) {
        if (node == null) {
            return null;
        }
        cur++;
        while (cur > dep && !stack.empty()) {
            stack.pop();
        }
        dep = Math.max(dep, cur);
        if (cur == dep) {
            stack.push(node);
        }
        dfs(node.left, cur);
        dfs(node.right, cur);
        return lowestCommonAncestor(node, stack);
    }

    /**
     * 获取最近公共祖先
     */
    public TreeNode lowestCommonAncestor(TreeNode node, Stack<TreeNode> stack) {
        if (node == null || stack.contains(node)) {
            return node;
        }
        TreeNode left = lowestCommonAncestor(node.left, stack);
        TreeNode right = lowestCommonAncestor(node.right, stack);
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return node;
        }
    }
}
